package com.datastructure.test.open;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Open {

    public static void main(String[] args) {

    }

    public int open (ArrayList<String> vec, String tar) {
        // write code here
        LinkedList<String> queue = new LinkedList<>();
        queue.add("0000");
        List<String> visited = new ArrayList<>();
        visited.add("0000");
        int step = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            System.out.println(step);
            System.out.println(queue);
            for(int i=0;i<size;i++){
                String key = queue.poll();
                if(vec.contains(key)){
                    continue;
                } else if(tar.equals(key)) {
                    return step;
                }
                for(int j=0;j<4;j++){
                    String plusStep = plus(key,j);
                    if(!visited.contains(plusStep)){
                        visited.add(plusStep);
                        queue.add(plusStep);
                    }
                    String minusStep = minus(key,j);
                    if(!visited.contains(minusStep)){
                        visited.add(minusStep);
                        queue.add(minusStep);
                    }
                }
            }
            step++;
        }
        return -1;
    }

    public String plus(String key,int i){
        char[] chars= key.toCharArray();
        if(chars[i]=='9'){
            chars[i] = '0';
        } else {
            chars[i]+=1;
        }
        return new String(chars);
    }

    public String minus(String key,int i){
        char[] chars= key.toCharArray();
        if(chars[i]=='0'){
            chars[i] = '9';
        } else {
            chars[i] -= 1;
        }
        return new String(chars);
    }
}
